home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / incl / LEDA.020+881 / impl / olist1.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  2.8 KB  |  116 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  olist1.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_OLIST1_H
  17. #define LEDA_OLIST1_H
  18.  
  19. //------------------------------------------------------------------------------
  20. //  doubly linked circular lists
  21. //------------------------------------------------------------------------------
  22.  
  23. #include <LEDA/basic.h>
  24.  
  25. //------------------------------------------------------------------------------
  26. // class olink1 (base class for all list items)
  27. //------------------------------------------------------------------------------
  28.  
  29. class olink1 {
  30.  
  31.   olink1* succ;
  32.   olink1* pred;
  33.  
  34. public:
  35.  
  36.   olink1* succ_item() { return succ; }
  37.   olink1* pred_item() { return pred; }
  38.  
  39.   void    del_item() { olink1*  p = pred;
  40.                        olink1*  s = succ;
  41.                        p->succ = s;
  42.                        s->pred = p; }
  43.  
  44.   LEDA_MEMORY(olink1)
  45.  
  46.   friend class olist1;
  47.  
  48. };
  49.  
  50.  
  51. //------------------------------------------------------------------------------
  52. // olist1: base class for all doubly linked lists
  53. //------------------------------------------------------------------------------
  54.  
  55. class olist1 : public olink1 {
  56.  
  57. public:
  58.  
  59.  
  60. // access operations
  61.  
  62.    bool empty()  const { return (succ==this) ? true : false;}
  63.  
  64.    olink1* first()                const { return (succ==this) ? nil : succ; }
  65.    olink1* last()                 const { return (pred==this) ? nil : pred; }
  66.    olink1* first_item()           const { return first(); }
  67.    olink1* last_item()            const { return last(); }
  68.    olink1* next_item(olink1* p)   const { return succ(p); }
  69.  
  70.    olink1* succ(olink1* p) const { return (p->succ==this)? nil : p->succ; }
  71.    olink1* pred(olink1* p) const { return (p->pred==this)? nil : p->pred; }
  72.    olink1* cyclic_succ(olink1* p) const { return (p->succ==this) ? pred : p->succ; }
  73.    olink1* cyclic_pred(olink1* p) const { return (p->pred==this) ? succ : p->pred; }
  74.  
  75. // update operations
  76.  
  77.    void    insert(olink1* p, olink1* l);
  78.    olink1* del(olink1* loc);
  79.  
  80.    olink1* push(olink1* p)   { insert(p,this); }
  81.    olink1* append(olink1* p) { insert(p,pred); }
  82.  
  83.    olink1* pop()     { return del(succ); }
  84.    olink1* Pop()     { return del(pred); }
  85.  
  86.    void clear() { succ = pred = this; }
  87.  
  88.  
  89. // constructors & destructors
  90.  
  91.    olist1()  { succ = pred = this; }
  92.   ~olist1()  { clear(); }
  93.  
  94. };
  95.  
  96.  
  97. inline void olist1::insert(olink1* n, olink1* p) 
  98. { // insert n insert after p
  99.   olink1* s=p->succ;
  100.   n->pred = p;
  101.   n->succ = s;
  102.   p->succ = n;
  103.   s->pred = n;
  104.  }
  105.  
  106. inline olink1* olist1::del(olink1* x)
  107. { olink1*  p = x->pred;
  108.   olink1*  s = x->succ;
  109.   p->succ = s;
  110.   s->pred = p;
  111.   return x;
  112.  }
  113.  
  114.  
  115. #endif
  116.